{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Construct Smallest Number From DI String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #greedy #string #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #贪心 #字符串 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: smallestNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #根据模式串构造最小数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你下标从 <strong>0</strong> 开始、长度为 <code>n</code>&nbsp;的字符串&nbsp;<code>pattern</code>&nbsp;，它包含两种字符，<code>'I'</code>&nbsp;表示 <strong>上升</strong>&nbsp;，<code>'D'</code>&nbsp;表示 <strong>下降</strong>&nbsp;。</p>\n",
    "\n",
    "<p>你需要构造一个下标从 <strong>0</strong>&nbsp;开始长度为&nbsp;<code>n + 1</code>&nbsp;的字符串，且它要满足以下条件：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>num</code>&nbsp;包含数字&nbsp;<code>'1'</code>&nbsp;到&nbsp;<code>'9'</code>&nbsp;，其中每个数字&nbsp;<strong>至多</strong>&nbsp;使用一次。</li>\n",
    "\t<li>如果&nbsp;<code>pattern[i] == 'I'</code>&nbsp;，那么&nbsp;<code>num[i] &lt; num[i + 1]</code>&nbsp;。</li>\n",
    "\t<li>如果&nbsp;<code>pattern[i] == 'D'</code>&nbsp;，那么&nbsp;<code>num[i] &gt; num[i + 1]</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回满足上述条件字典序 <strong>最小</strong>&nbsp;的字符串<em>&nbsp;</em><code>num</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>pattern = \"IIIDIDDD\"\n",
    "<b>输出：</b>\"123549876\"\n",
    "<strong>解释：\n",
    "</strong>下标 0 ，1 ，2 和 4 处，我们需要使 num[i] &lt; num[i+1] 。\n",
    "下标 3 ，5 ，6 和 7 处，我们需要使 num[i] &gt; num[i+1] 。\n",
    "一些可能的 num 的值为 \"245639871\" ，\"135749862\" 和 \"123849765\" 。\n",
    "\"123549876\" 是满足条件最小的数字。\n",
    "注意，\"123414321\" 不是可行解因为数字 '1' 使用次数超过 1 次。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>pattern = \"DDD\"\n",
    "<b>输出：</b>\"4321\"\n",
    "<strong>解释：</strong>\n",
    "一些可能的 num 的值为 \"9876\" ，\"7321\" 和 \"8742\" 。\n",
    "\"4321\" 是满足条件最小的数字。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= pattern.length &lt;= 8</code></li>\n",
    "\t<li><code>pattern</code>&nbsp;只包含字符&nbsp;<code>'I'</code> 和&nbsp;<code>'D'</code> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [construct-smallest-number-from-di-string](https://leetcode.cn/problems/construct-smallest-number-from-di-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [construct-smallest-number-from-di-string](https://leetcode.cn/problems/construct-smallest-number-from-di-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"IIIDIDDD\"', '\"DDD\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        digits: str = list(\"98765432\")\n",
    "        result: List[str] = [\"1\"]\n",
    "        rev: List[str] = []\n",
    "        isFirstD: bool = True\n",
    "\n",
    "        for di in pattern:\n",
    "            if di == \"I\":\n",
    "                isFirstD = True\n",
    "                while len(rev) > 0:\n",
    "                    result.append(rev.pop())\n",
    "                result.append(digits.pop())\n",
    "            else:\n",
    "                if isFirstD:\n",
    "                    rev.append(result.pop())\n",
    "                    isFirstD = False\n",
    "                rev.append(digits.pop())\n",
    "\n",
    "        while len(rev) > 0:\n",
    "            result.append(rev.pop())\n",
    "\n",
    "        return \"\".join(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        n,i=len(pattern),0\n",
    "        ans=[str(i) for i in range(1,n+2)]\n",
    "        while i<n:\n",
    "            t=i\n",
    "            while i<n and pattern[i]=='D':\n",
    "                i+=1\n",
    "            ans[t:i+1]=reversed(ans[t:i+1])\n",
    "            i+=1\n",
    "        return \"\".join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        n = len(pattern)\n",
    "        ans = list(digits[1:n+2])\n",
    "        \n",
    "        i = 0\n",
    "        while i<n:\n",
    "            if pattern[i] == 'I':\n",
    "                i += 1\n",
    "                continue\n",
    "            D_statr = i\n",
    "            i += 1 \n",
    "            # 找到第一个D下标\n",
    "            while i < n and pattern[i] == 'D':\n",
    "                i += 1\n",
    "            ans[D_statr:i+1] = ans[D_statr:i+1][::-1]\n",
    "\n",
    "        return ''.join(ans)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        n = len(pattern)\n",
    "        ans = list(digits[1:n + 2])\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            while i < n and pattern[i] == 'I':\n",
    "                i += 1\n",
    "            i0 = i\n",
    "            i += 1\n",
    "            while i < n and pattern[i] == 'D':\n",
    "                i += 1\n",
    "            ans[i0:i + 1] = ans[i0:i + 1][::-1]\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        i, cur, n = 0, 1, len(pattern)\n",
    "        ans = [''] * (n + 1)\n",
    "        while i < n:\n",
    "            if i and pattern[i] == 'I':\n",
    "                i += 1\n",
    "            while i < n and pattern[i] == 'I':\n",
    "                ans[i] = digits[cur]\n",
    "                cur += 1\n",
    "                i += 1\n",
    "            i0 = i\n",
    "            while i < n and pattern[i] == 'D':\n",
    "                i += 1\n",
    "            for j in range(i, i0 - 1, -1):\n",
    "                ans[j] = digits[cur]\n",
    "                cur += 1\n",
    "        return ''.join(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        w = len(pattern)\n",
    "        res = [str(x) for x in range(1, w+2)]\n",
    "        cur = 0\n",
    "        while cur != w:\n",
    "            if pattern[cur] == \"D\":\n",
    "                next_cur = cur\n",
    "                while next_cur < w and pattern[next_cur] == \"D\":\n",
    "                    next_cur += 1\n",
    "                res[cur:next_cur+1] = res[cur:next_cur+1][::-1]\n",
    "                cur = next_cur\n",
    "            else:\n",
    "                cur += 1\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        lenp = len(pattern)\n",
    "        res = list(range(1,lenp+2))\n",
    "        i=0\n",
    "        while i<lenp:\n",
    "            if pattern[i]=='I':\n",
    "                i += 1\n",
    "            else:\n",
    "                start=i\n",
    "                while i<lenp and pattern[i]=='D':\n",
    "                    i += 1\n",
    "                res[start:i+1] = res[start:i+1][::-1]\n",
    "        return ''.join([str(x) for x in res])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        res = [1]*(len(pattern) + 1)\n",
    "        for i, c in enumerate(pattern, 1):\n",
    "            if c == 'I':\n",
    "                res[i] = i + 1\n",
    "            else:\n",
    "                off = res.index(i)\n",
    "                res[off+1:i+1] = res[off:i]\n",
    "                res[off] = i+1\n",
    "            # print(c, res[:i+1])\n",
    "        return ''.join(map(str, res))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        n = len(pattern)\n",
    "        ans = [0] * (n+1)\n",
    "        cur = 1\n",
    "        stack = []\n",
    "        j = 0\n",
    "        for i in range(n):\n",
    "            if pattern[i] == 'D':\n",
    "                stack.append(cur)\n",
    "            else:\n",
    "                ans[j] = cur\n",
    "                j += 1\n",
    "                while stack:\n",
    "                    ans[j] = stack.pop()\n",
    "                    j += 1\n",
    "            cur += 1\n",
    "        stack.append(cur)\n",
    "        while stack:\n",
    "            ans[j] = stack.pop()\n",
    "            j += 1\n",
    "        return ''.join(map(str, ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "      m = len(pattern)\n",
    "      ans = [str(i+1) for i in range(m+1)]\n",
    "      cur = 0\n",
    "      for i in range(1,len(ans)):\n",
    "        if pattern[i-1]=='D':\n",
    "          temp = ans[i]\n",
    "          ans.pop(i)\n",
    "          ans.insert(cur,temp)\n",
    "        else:\n",
    "          cur = i\n",
    "      return ''.join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        n = len(pattern)\n",
    "        ans = list(digits[1 : n + 2])\n",
    "        i = 0  # 维护当前走到哪里\n",
    "        while i < n:\n",
    "            if pattern[i] == 'I':\n",
    "                i += 1\n",
    "                continue\n",
    "            i0 = i # D的起点\n",
    "            i += 1\n",
    "            while i < n and pattern[i] == 'D':\n",
    "                i += 1\n",
    "            # 翻转\n",
    "            ans[i0 : i + 1] = ans[i0: i + 1][::-1]\n",
    "        \n",
    "        # 这个''.join太秀了\n",
    "        return ''.join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        res = []\n",
    "        stk = []\n",
    "        num = 1\n",
    "        for i in range(len(pattern)):\n",
    "            if pattern[i]=='D':\n",
    "                stk.append(num)\n",
    "            else:\n",
    "                res.append(str(num))\n",
    "                while stk:\n",
    "                    res.append(str(stk.pop()))\n",
    "\n",
    "            num += 1\n",
    "\n",
    "        stk.append(num)\n",
    "        while stk:\n",
    "            res.append(str(stk.pop()))\n",
    "\n",
    "        return \"\".join(res)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        listD = []\n",
    "        flagD = 0\n",
    "        flagI = 0\n",
    "        for _ in range(len(pattern)):\n",
    "            if pattern[_] == \"D\":\n",
    "                flagD = flagD+1\n",
    "            elif pattern[_] != \"D\" and flagD!=0:\n",
    "                listD.append(flagD)\n",
    "                flagD = 0\n",
    "            if pattern[_] == \"I\":\n",
    "                flagI = flagI-1\n",
    "            elif pattern[_] != \"I\" and flagI!=0:\n",
    "                listD.append(flagI)\n",
    "                flagI = 0\n",
    "            if _ == len(pattern)-1:\n",
    "                if flagD!=0:\n",
    "                    listD.append(flagD)\n",
    "                elif flagI!=0:\n",
    "                    listD.append(flagI)\n",
    "        if listD[0]>0:\n",
    "            initn = listD[0]+1\n",
    "        else:\n",
    "            initn = 1\n",
    "        maxn = initn\n",
    "        ans = [initn]\n",
    "        for i in range(len(listD)):\n",
    "            for _ in range(abs(listD[i])):\n",
    "                if listD[i]>0:\n",
    "                    initn = initn -1\n",
    "                    ans.append(initn)\n",
    "                elif listD[i]<0:\n",
    "                    initn = initn + 1\n",
    "                    maxn = max(maxn,initn)\n",
    "                    ans.append(initn)\n",
    "            if i != len(listD)-1:\n",
    "                if listD[i+1] <0:\n",
    "                    initn = maxn\n",
    "                elif listD[i+1] >0:\n",
    "                    ans[-1] = ans[-1] + listD[i+1]\n",
    "                    initn = ans[-1]\n",
    "                    maxn = max(maxn, initn)\n",
    "        ans2=\"\"\n",
    "        for _ in range(len(ans)):\n",
    "            ans2 = ans2 + str(ans[_])\n",
    "        return ans2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        # 方法1、贪心\n",
    "        i = 0\n",
    "        cur = 1\n",
    "        n = len(pattern)\n",
    "        ans = [\"\"]*(n + 1)\n",
    "        while i < n:\n",
    "            if i and pattern[i] == \"I\":\n",
    "                i += 1\n",
    "            while i < n and pattern[i] == \"I\":\n",
    "                ans[i] += str(cur)\n",
    "                cur += 1\n",
    "                i += 1\n",
    "            i0 = i\n",
    "            while i < n and pattern[i] == \"D\":\n",
    "                i += 1\n",
    "            for j in range(i,i0 - 1, -1):\n",
    "                ans[j] += str(cur)\n",
    "                cur += 1\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        n = len(pattern)\n",
    "        res = [str(i + 1) for i in range(n + 1)]\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if pattern[i] == 'I':\n",
    "                i += 1\n",
    "                continue \n",
    "            j = i \n",
    "            while j < n and pattern[j] == 'D':\n",
    "                j += 1 \n",
    "            res[i : j + 1] = res[i : j + 1][::-1]\n",
    "            i = j \n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        n = len(pattern)\n",
    "        ans = list(digits[1: n + 2])\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if pattern[i] == 'I':\n",
    "                i += 1\n",
    "                continue\n",
    "            i0 = i\n",
    "            while i < n and pattern[i] == 'D':\n",
    "                i += 1\n",
    "            ans[i0: i + 1] = ans[i0: i + 1][::-1]\n",
    "        return ''.join(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        n,i=len(pattern),0\n",
    "        ans=[str(i) for i in range(1,n+2)]\n",
    "        while i<n:\n",
    "            t=i\n",
    "            while i<n and pattern[i]=='D':\n",
    "                i+=1\n",
    "            ans[t:i+1]=reversed(ans[t:i+1])\n",
    "            i+=1\n",
    "        return \"\".join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        pattern += 'I'\n",
    "        # 沿着I往右走，遇到D时，找到下一个I并转换方向，遇到下一个I时回到之前的I继续往右走\n",
    "\n",
    "        i = 0\n",
    "        cnt = 1\n",
    "        n = len(pattern)\n",
    "        ans = [0] * n\n",
    "\n",
    "        def step(direction):\n",
    "            # 走一步，direction表示方向\n",
    "            nonlocal cnt, i\n",
    "            ans[i] = str(cnt)\n",
    "            cnt += 1\n",
    "            i += direction\n",
    "\n",
    "        while i < n:\n",
    "            if pattern[i] == 'I':\n",
    "                step(1)\n",
    "            else:\n",
    "                # 踏入虚空\n",
    "                while pattern[i] == 'D':\n",
    "                    i += 1\n",
    "                flag = i + 1\n",
    "                # 时间回溯\n",
    "                step(-1)\n",
    "                while pattern[i] == 'D':\n",
    "                    step(-1)\n",
    "                # 瞬间移动\n",
    "                i = flag\n",
    "        return ''.join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        D_num = 0 \n",
    "        cur = 1\n",
    "        ans = []\n",
    "        for p in pattern:\n",
    "            if p=='D':\n",
    "                D_num+=1\n",
    "            else:\n",
    "                ans.extend(list(range(cur+D_num, cur-1, -1)))\n",
    "                cur += D_num+1\n",
    "                D_num = 0\n",
    "        ans.extend(range(cur+D_num, cur-1, -1))\n",
    "        return ''.join([str(x) for x in ans])\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def huishu(self,temp, pattern,res):\n",
    "        if len(res):\n",
    "            return\n",
    "        if len(temp)==len(pattern)+1:\n",
    "            \n",
    "            for i in temp:\n",
    "                res.append(i)\n",
    "            # print(res,666666)\n",
    "            return\n",
    "        zuihouyigeshuzi= temp[-1]\n",
    "        temp_changdu= len(temp)\n",
    "        shangsheng_xiajiang= pattern[temp_changdu-1]\n",
    "        # print(zuihouyigeshuzi, shangsheng_xiajiang,33333333)\n",
    "        # print(res,777777665555555)\n",
    "        if shangsheng_xiajiang=='I':\n",
    "            # shangsheng\n",
    "            for i in range(zuihouyigeshuzi+1,10):\n",
    "                if i in temp:\n",
    "                    continue\n",
    "                temp.append(i)\n",
    "                # if len(temp)==len(pattern)+1:break\n",
    "                # print(res,6665555555)\n",
    "                self.huishu(temp, pattern,res)\n",
    "                temp.pop()\n",
    "        else: \n",
    "            #xiajiang\n",
    "            for i in range(1,zuihouyigeshuzi):\n",
    "                if i in temp:\n",
    "                    continue\n",
    "                temp.append(i)\n",
    "                # if len(temp)==len(pattern)+1:break\n",
    "                self.huishu(temp, pattern,res)\n",
    "                temp.pop()\n",
    "            \n",
    "       \n",
    "        \n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        temp=[]\n",
    "        res=[]\n",
    "        # temp 中含有第一个元素\n",
    "        for i in range(1,10):\n",
    "            temp.append(i)\n",
    "            self.huishu(temp, pattern,res)\n",
    "            temp.pop()\n",
    "        # print(res,555555)\n",
    "        xx=''\n",
    "        for i in res:\n",
    "            xx+=str(i)\n",
    "        print(xx)\n",
    "        return xx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        n = len(pattern)\n",
    "        ans = list(digits[1:n+2])\n",
    "        i = 0\n",
    "        while i<n:\n",
    "            if pattern[i]=='I':\n",
    "                i += 1\n",
    "                continue\n",
    "            i0 = i\n",
    "            i += 1\n",
    "            while i<n and pattern[i]=='D':\n",
    "                i += 1\n",
    "            ans[i0:i+1] = ans[i0:i+1][::-1]\n",
    "        return \"\".join(ans)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        pattern += 'I'\n",
    "        # 从左往右走，沿着I往右，遇到D时，找到下一个I并转换方向，遇到下一个I时回到之前的I继续往右走\n",
    "\n",
    "        i = 0\n",
    "        cnt = 1\n",
    "        n = len(pattern)\n",
    "        ans = [0] * n\n",
    "\n",
    "        def step(v):\n",
    "            nonlocal cnt, i\n",
    "            ans[i] = str(cnt)\n",
    "            cnt += 1\n",
    "            i += v\n",
    "            \n",
    "        while i < n:\n",
    "            if pattern[i] == 'I':\n",
    "                step(1)\n",
    "            else:# 找到下一个I\n",
    "                while pattern[i] == 'D':\n",
    "                    i += 1\n",
    "                # 记录这个位置后的位置\n",
    "                flag = i + 1\n",
    "                # 往回走\n",
    "                step(-1)\n",
    "                while pattern[i] == 'D':\n",
    "                    step(-1)\n",
    "                # 回到旗标\n",
    "                i = flag\n",
    "        return ''.join(ans)\n",
    "    \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "\n",
    "        n = len(pattern)\n",
    "        nums = [str(i) for i in range(1, n+2)]\n",
    "        ans = ''\n",
    "        count = 0\n",
    "        for i, op in enumerate(pattern):\n",
    "            \n",
    "            if op == 'I':\n",
    "\n",
    "                while count:\n",
    "                    ans += nums.pop(count)\n",
    "                    count -= 1\n",
    "\n",
    "                ans += nums.pop(0)\n",
    "            else:\n",
    "                count += 1\n",
    "\n",
    "        while count:\n",
    "            ans += nums.pop(count)\n",
    "            count -= 1            \n",
    "        ans += nums[0]\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        x=1\n",
    "        st=[]\n",
    "        la=[]\n",
    "        for c in pattern:\n",
    "            if c=='D':\n",
    "                st.append(x)\n",
    "            else:\n",
    "                la.append(x)\n",
    "                while st:\n",
    "                    la.append(st.pop())\n",
    "            x+=1\n",
    "        st.append(x)\n",
    "        while st:\n",
    "            la.append(st.pop())\n",
    "        return ''.join(map(str,la))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        n = len(pattern)\n",
    "        tmp = list()\n",
    "        result = None\n",
    "        seen = set()\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal result\n",
    "            if i == n + 1:\n",
    "                result = \"\".join(map(lambda x: str(x), tmp))\n",
    "                return True\n",
    "            for j in range(1, 10):\n",
    "                if j not in seen:\n",
    "                    if (i == 0) or (pattern[i-1] == \"I\" and j > tmp[-1]) or (pattern[i-1] == \"D\" and j < tmp[-1]):\n",
    "                        tmp.append(j)\n",
    "                        seen.add(j)\n",
    "                        if dfs(i+1):\n",
    "                            return True\n",
    "                        tmp.pop()\n",
    "                        seen.remove(j)\n",
    "            return False\n",
    "\n",
    "        dfs(0)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        # 方法2、回溯\n",
    "        def dfs(idx,path):\n",
    "            nonlocal res\n",
    "            if idx == n + 1:\n",
    "                res = min(res,\"\".join(path))\n",
    "                return\n",
    "            p = set(path)\n",
    "            for i in range(1,10):\n",
    "                if str(i) in p:\n",
    "                    continue\n",
    "                if idx == 0 or (pattern[idx - 1] == \"I\" and str(i) > path[-1]) or (pattern[idx - 1] == \"D\" and str(i) < path[-1]):\n",
    "                    dfs(idx + 1,path + [str(i)])\n",
    "\n",
    "        n = len(pattern)\n",
    "        res = \"9\" * (n + 1)\n",
    "        dfs(0,[])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        ans = []\n",
    "        c = 0\n",
    "        current = 1\n",
    "        for p in pattern:\n",
    "            if p == 'D':\n",
    "                c += 1\n",
    "            else:\n",
    "                ans.extend(range(current + c, current - 1, -1))\n",
    "                current += c + 1\n",
    "                c = 0\n",
    "        ans.extend(range(current + c, current - 1, -1))\n",
    "        return ''.join(str(i) for i in ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        s = '123456789'\n",
    "        res = ''\n",
    "        left, right = 0, 1\n",
    "        for c in pattern:\n",
    "            if c == 'I':\n",
    "                res += s[left:right][::-1]\n",
    "                left, right = right, right + 1\n",
    "            else:\n",
    "                right += 1\n",
    "        res += s[left:right][::-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        n = len(pattern)\n",
    "        tmp = list()\n",
    "        result = None\n",
    "        seen = set()\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal result\n",
    "            if i == n + 1:\n",
    "                result = \"\".join(map(lambda x: str(x), tmp))\n",
    "                return True\n",
    "            for j in range(1, 10):\n",
    "                if j not in seen:\n",
    "                    if (i == 0) or (pattern[i-1] == \"I\" and j > tmp[-1]) or (pattern[i-1] == \"D\" and j < tmp[-1]):\n",
    "                        tmp.append(j)\n",
    "                        seen.add(j)\n",
    "                        if dfs(i+1):\n",
    "                            return True\n",
    "                        tmp.pop()\n",
    "                        seen.remove(j)\n",
    "            return False\n",
    "\n",
    "        dfs(0)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "\n",
    "\n",
    "        n = len(pattern)\n",
    "\n",
    "\n",
    "        res = list(digits[1: n +2])\n",
    "        i = 0\n",
    "        while i < n:\n",
    "\n",
    "\n",
    "            if pattern[i] == \"I\":\n",
    "                i += 1\n",
    "                continue\n",
    "            i0 = i\n",
    "            i += 1\n",
    "\n",
    "            while i < n and pattern[i] == \"D\":\n",
    "                i += 1\n",
    "            \n",
    "            res[i0:i + 1] = res[i0:i+1][::-1]\n",
    "\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "\n",
    "        i, cur, n = 0, 1, len(pattern)\n",
    "\n",
    "\n",
    "        res = [''] * ( n + 1)\n",
    "\n",
    "        while i < n:\n",
    "            if i and pattern[i] == \"I\":\n",
    "                i += 1\n",
    "            while i < n and pattern[i] == \"I\":\n",
    "                res[i] = str(cur)\n",
    "                cur += 1\n",
    "                i += 1\n",
    "            i0 = i\n",
    "            while i < n and pattern[i] == \"D\":\n",
    "                i += 1\n",
    "            for j in range(i, i0 - 1, -1):\n",
    "                res[j] = str(cur)\n",
    "                cur += 1\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        n = len(pattern)\n",
    "        ans = [str(i) for i in range(1, n + 2)]\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if pattern[i] == 'I':\n",
    "                i += 1\n",
    "                continue\n",
    "            i0 = i\n",
    "            i += 1\n",
    "            while i < n and pattern[i] == 'D':\n",
    "                i += 1\n",
    "            ans[i0:i+1] = ans[i0:i+1][::-1]\n",
    "        return ''.join(ans)\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        n = len(pattern)\n",
    "        s = list(\"123456789\"[:n + 1])\n",
    "        left = 0\n",
    "        while left < n:\n",
    "            if pattern[left] == \"I\":\n",
    "                left += 1\n",
    "                continue\n",
    "            start = left\n",
    "            left += 1\n",
    "            while left < n and pattern[left] == \"D\":\n",
    "                left += 1\n",
    "            s[start:left+1] = s[start:left+1][::-1]\n",
    "        return \"\".join(s)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        # 方法2、回溯\n",
    "        def dfs(idx,path):\n",
    "            nonlocal res\n",
    "            if idx == n + 1:\n",
    "                res = min(res,path)\n",
    "                return\n",
    "            p = path\n",
    "            for i in range(1,10):\n",
    "                if str(i) in p:\n",
    "                    continue\n",
    "                if idx == 0 or (pattern[idx - 1] == \"I\" and str(i) > path[-1]) or (pattern[idx - 1] == \"D\" and str(i) < path[-1]):\n",
    "                    dfs(idx + 1,path + str(i))\n",
    "\n",
    "        n = len(pattern)\n",
    "        res = \"9\" * (n + 1)\n",
    "        dfs(0,\"\")\n",
    "        return res\n",
    "\n",
    "        n = len(pattern)\n",
    "        res = \"9\" * (n + 1)\n",
    "        dfs(0,[])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        i, cur, n = 0, 1, len(pattern)\n",
    "        ans = [''] * (n + 1)\n",
    "        while i < n:\n",
    "            if i and pattern[i] == 'I':\n",
    "                i += 1\n",
    "            while i < n and pattern[i] == 'I':\n",
    "                ans[i] = digits[cur]\n",
    "                cur += 1\n",
    "                i += 1\n",
    "            i0 = i\n",
    "            while i < n and pattern[i] == 'D':\n",
    "                i += 1\n",
    "            for j in range(i, i0 - 1, -1):\n",
    "                ans[j] = digits[cur]\n",
    "                cur += 1\n",
    "        return ''.join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        n = len(pattern)\n",
    "        tmp = list()\n",
    "        result = None\n",
    "        seen = set()\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal result\n",
    "            if i == n + 1:\n",
    "                result = \"\".join(map(lambda x: str(x), tmp))\n",
    "                return True\n",
    "            for j in range(1, 10):\n",
    "                if j not in seen:\n",
    "                    if (i == 0) or (pattern[i-1] == \"I\" and j > tmp[-1]) or (pattern[i-1] == \"D\" and j < tmp[-1]):\n",
    "                        tmp.append(j)\n",
    "                        seen.add(j)\n",
    "                        if dfs(i+1):\n",
    "                            return True\n",
    "                        tmp.pop()\n",
    "                        seen.remove(j)\n",
    "            return False\n",
    "\n",
    "        dfs(0)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        n = len(pattern)\n",
    "        res = [str(i + 1) for i in range(n + 1)]\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if pattern[i] == 'I':\n",
    "                i += 1 \n",
    "                continue \n",
    "            j = i \n",
    "            while j < n and pattern[j] == 'D':\n",
    "                j += 1 \n",
    "            res[i : j + 1] = res[i : j + 1][::-1]\n",
    "            i = j \n",
    "        return ''.join(res) \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "\n",
    "        ans = []\n",
    "        def dfs(path, cur, seen):\n",
    "            if cur == len(pattern):\n",
    "                ans.append(''.join(map(str, path)))\n",
    "                return True\n",
    "\n",
    "            if pattern[cur] == 'I':\n",
    "                for i in range(path[-1] + 1, 10):\n",
    "                    if i not in seen:\n",
    "                        path.append(i)\n",
    "                        seen.add(i)\n",
    "                        if dfs(path, cur + 1, seen):\n",
    "                            return True\n",
    "                        seen.remove(i)\n",
    "                        path.pop()\n",
    "            elif pattern[cur] == 'D':\n",
    "                for i in range(1, path[-1]):\n",
    "                    if i not in seen:\n",
    "                        path.append(i)\n",
    "                        seen.add(i)\n",
    "                        if dfs(path, cur + 1, seen):\n",
    "                            return True\n",
    "                        seen.remove(i)\n",
    "                        path.pop()\n",
    "\n",
    "\n",
    "            return False\n",
    "            \n",
    "\n",
    "        for i in range(1, 10):\n",
    "            if dfs([i], 0, set([i])):\n",
    "                break\n",
    "\n",
    "\n",
    "\n",
    "        return ans[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        stack = []\n",
    "        num = 1\n",
    "        ans = \"\"\n",
    "        for i in range(len(pattern)):\n",
    "            if pattern[i] == 'D':\n",
    "                stack.append(num)\n",
    "            elif pattern[i] == 'I':\n",
    "                ans += str(num)\n",
    "                while stack:\n",
    "                    ans += str(stack.pop())\n",
    "            num += 1\n",
    "        \n",
    "        stack.append(num)\n",
    "        while stack:\n",
    "            ans += str(stack.pop())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        n = len(pattern)\n",
    "        tmp = list()\n",
    "        result = None\n",
    "        seen = set()\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal result\n",
    "            if i == n + 1:\n",
    "                result = \"\".join(map(lambda x: str(x), tmp))\n",
    "                return True\n",
    "            for j in range(1, 10):\n",
    "                if j not in seen:\n",
    "                    if (i == 0) or (pattern[i-1] == \"I\" and j > tmp[-1]) or (pattern[i-1] == \"D\" and j < tmp[-1]):\n",
    "                        tmp.append(j)\n",
    "                        seen.add(j)\n",
    "                        if dfs(i+1):\n",
    "                            return True\n",
    "                        tmp.pop()\n",
    "                        seen.remove(j)\n",
    "            return False\n",
    "\n",
    "        dfs(0)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        n = len(pattern)\n",
    "        ans = list(digits[1:n + 2])\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            while i < n and pattern[i] == 'I':\n",
    "                i += 1\n",
    "            i0 = i\n",
    "            while i < n and pattern[i] == 'D':\n",
    "                i += 1\n",
    "            ans[i0:i+1] = ans[i0:i+1][::-1]\n",
    "            \n",
    "        return ''.join(ans)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        res, stack = [],[]\n",
    "        for i,c in enumerate(pattern+'I', 1):\n",
    "            stack += str(i)\n",
    "            if c == 'I':\n",
    "                res += stack[::-1]\n",
    "                stack = []\n",
    "        \n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import permutations\n",
    "class Solution:\n",
    "    def isRightStr(self,numStr,pattern):\n",
    "        # print(numStr,pattern)\n",
    "        if len(numStr)!=len(pattern)+1:\n",
    "            return False\n",
    "        for i in range(len(pattern)):\n",
    "            if pattern[i]=='I' and numStr[i]>=numStr[i+1]:\n",
    "                return False\n",
    "            elif pattern[i]=='D' and numStr[i]<=numStr[i+1]:\n",
    "                return False\n",
    "        return True\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        allNum=[str(i) for i in range(1,len(pattern)+2)]\n",
    "        allNumStr=permutations(allNum,len(allNum))\n",
    "        res='999999999'\n",
    "        for s in allNumStr:\n",
    "            # print(allNumStr,s)\n",
    "            numStr=''.join(s)\n",
    "            if self.isRightStr(numStr,pattern):\n",
    "                res=numStr if int(numStr)<int(res) else res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        n = len(pattern)\n",
    "        ans = [chr(ord('0') + i) for i in range(1, n + 2)]\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            while i < n and pattern[i] == 'I':\n",
    "                i += 1\n",
    "            i0 = i\n",
    "            while i < n and pattern[i] == 'D':\n",
    "                i += 1\n",
    "            ans[i0: i + 1] = ans[i0: i + 1][::-1]\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        pattern += 'I'\n",
    "        # 沿着I往右走，遇到D时，找到下一个I并转换方向，遇到下一个I时回到之前的I继续往右走\n",
    "\n",
    "        i = 0\n",
    "        cnt = 1\n",
    "        n = len(pattern)\n",
    "        ans = [0] * n\n",
    "\n",
    "        def step(direction):\n",
    "            # 步进，direction控制方向\n",
    "            nonlocal cnt, i\n",
    "            ans[i] = str(cnt)\n",
    "            cnt += 1\n",
    "            i += direction\n",
    "\n",
    "        while i < n:\n",
    "            if pattern[i] == 'I':\n",
    "                step(1)\n",
    "            else:\n",
    "                while pattern[i] == 'D':\n",
    "                    i += 1\n",
    "                flag = i + 1\n",
    "                step(-1)\n",
    "                while pattern[i] == 'D':\n",
    "                    step(-1)\n",
    "                i = flag\n",
    "        return ''.join(ans)\n",
    "    \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        n = len(pattern)\n",
    "        ans = list(digits[1:n+2])\n",
    "        i=0\n",
    "        while i<n:\n",
    "            if pattern[i]=='I':\n",
    "                i+=1\n",
    "                continue\n",
    "            i0 = i\n",
    "            while i<n and pattern[i]=='D':\n",
    "                i+=1\n",
    "            ans[i0:i+1]=ans[i0:i+1][::-1]\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        n = len(pattern)\n",
    "        \n",
    "        res = \"\"\n",
    "        \n",
    "        rest = set([str(i) for i in range(1, n + 2)])\n",
    "        \n",
    "        def dfs(s, i):\n",
    "            nonlocal res\n",
    "            \n",
    "            if i == n:\n",
    "                if not res: \n",
    "                    res = s\n",
    "                    return\n",
    "            \n",
    "                res = min(res, s)\n",
    "                return\n",
    "            \n",
    "            if pattern[i] == \"I\":\n",
    "                for c in rest:\n",
    "                    if s[-1] < c:\n",
    "                        rest.remove(c)\n",
    "                        dfs(s + c, i + 1)\n",
    "                        rest.add(c)\n",
    "            if pattern[i] == \"D\":\n",
    "                for c in rest:\n",
    "                    if s[-1] > c:\n",
    "                        rest.remove(c)\n",
    "                        dfs(s + c, i + 1)\n",
    "                        rest.add(c)\n",
    "                \n",
    "            \n",
    "        \n",
    "        for i in range(1, n + 2):\n",
    "            rest.remove(str(i))\n",
    "            dfs(str(i), 0)\n",
    "            rest.add(str(i))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        n = len(pattern)\n",
    "        tmp = list()\n",
    "        result = None\n",
    "        seen = set()\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal result\n",
    "            if i == n + 1:\n",
    "                result = \"\".join(map(lambda x: str(x), tmp))\n",
    "                return True\n",
    "            for j in range(1, 10):\n",
    "                if j not in seen:\n",
    "                    if (i == 0) or (pattern[i-1] == \"I\" and j > tmp[-1]) or (pattern[i-1] == \"D\" and j < tmp[-1]):\n",
    "                        tmp.append(j)\n",
    "                        seen.add(j)\n",
    "                        if dfs(i+1):\n",
    "                            return True\n",
    "                        tmp.pop()\n",
    "                        seen.remove(j)\n",
    "            return False\n",
    "\n",
    "        dfs(0)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        # 方法2、回溯\n",
    "        def dfs(idx,path):\n",
    "            nonlocal res\n",
    "            if idx == n + 1:\n",
    "                res = min(res,path)\n",
    "                return\n",
    "            for i in range(1,10):\n",
    "                if str(i) in path:\n",
    "                    continue\n",
    "                if idx == 0 or (pattern[idx - 1] == \"I\" and str(i) > path[-1]) or (pattern[idx - 1] == \"D\" and str(i) < path[-1]):\n",
    "                    dfs(idx + 1,path + str(i))\n",
    "\n",
    "        n = len(pattern)\n",
    "        res = \"9\" * (n + 1)\n",
    "        dfs(0,\"\")\n",
    "        return res\n",
    "\n",
    "        n = len(pattern)\n",
    "        res = \"9\" * (n + 1)\n",
    "        dfs(0,[])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        n = len(pattern)\n",
    "        tmp = list()\n",
    "        result = None\n",
    "        seen = set()\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal result\n",
    "            if i == n + 1:\n",
    "                result = \"\".join(map(lambda x: str(x), tmp))\n",
    "                return True\n",
    "            for j in range(1, 10):\n",
    "                if j not in seen:\n",
    "                    if i == 0:\n",
    "                        tmp.append(j)\n",
    "                        seen.add(j)\n",
    "                        if dfs(i+1):\n",
    "                            return True\n",
    "                        tmp.pop()\n",
    "                        seen.remove(j)\n",
    "                    else:\n",
    "                        if (pattern[i-1] == \"I\" and j > tmp[-1]) or (pattern[i-1] == \"D\" and j < tmp[-1]):\n",
    "                            tmp.append(j)\n",
    "                            seen.add(j)\n",
    "                            if dfs(i+1):\n",
    "                                return True\n",
    "                            tmp.pop()\n",
    "                            seen.remove(j)\n",
    "            return False\n",
    "\n",
    "        dfs(0)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        n = len(pattern)\n",
    "        tmp = list()\n",
    "        result = None\n",
    "        seen = set()\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal result\n",
    "            if i == n + 1:\n",
    "                result = \"\".join(map(lambda x: str(x), tmp))\n",
    "                return True\n",
    "            for j in range(1, 10):\n",
    "                if j not in seen:\n",
    "                    if i == 0:\n",
    "                        tmp.append(j)\n",
    "                        seen.add(j)\n",
    "                        if dfs(i+1):\n",
    "                            return True\n",
    "                        tmp.pop()\n",
    "                        seen.remove(j)\n",
    "                    else:\n",
    "                        if (pattern[i-1] == \"I\" and j > tmp[-1]) or (pattern[i-1] == \"D\" and j < tmp[-1]):\n",
    "                            tmp.append(j)\n",
    "                            seen.add(j)\n",
    "                            if dfs(i+1):\n",
    "                                return True\n",
    "                            tmp.pop()\n",
    "                            seen.remove(j)\n",
    "            return False\n",
    "\n",
    "        dfs(0)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        n = len(pattern)\n",
    "        ans = list(digits[1:n+2])\n",
    "        i=0\n",
    "        while i<n:\n",
    "            if pattern[i]=='I':\n",
    "                i+=1\n",
    "                continue\n",
    "            i0 = i #记录D的起点\n",
    "            i+=1 \n",
    "            while i<n and pattern[i]=='D':\n",
    "                i+=1\n",
    "            ans[i0:i+1]=ans[i0:i+1][::-1] #翻转1234567变为1237654\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        n = len(pattern)\n",
    "        \n",
    "        def find(start,model):\n",
    "            nums = []\n",
    "            if model == 'I':\n",
    "                for i in range(start+1,10):\n",
    "                    nums.append(i)\n",
    "            else:\n",
    "                for i in range(start-1,0,-1):\n",
    "                    nums.append(i)\n",
    "            return nums\n",
    "        \n",
    "        \n",
    "        def dfs(index,stack,visited):\n",
    "            nonlocal ans\n",
    "            if ans:\n",
    "                return\n",
    "            if index == n:\n",
    "                #print(stack)\n",
    "                ans = ''.join([str(i) for i in stack])\n",
    "                return\n",
    "            nums = find(stack[index],pattern[index])\n",
    "            #print(f'可选参数 {nums}')\n",
    "            for x in nums:\n",
    "                if x in visited:\n",
    "                    continue\n",
    "                visited.add(x)\n",
    "                dfs(index+1,stack+[x],visited.copy())\n",
    "                visited.remove(x)\n",
    "        ans = ''\n",
    "        for i in range(1,10):\n",
    "            dfs(0,[i],{i})\n",
    "            if ans:\n",
    "                return ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, pattern: str) -> str:\n",
    "        i, cur, n = 0, 1, len(pattern)\n",
    "        ans = [''] * (n + 1)\n",
    "        while i < n:\n",
    "            if i and pattern[i] == 'I':\n",
    "                i += 1\n",
    "            while i < n and pattern[i] == 'I':\n",
    "                ans[i] = digits[cur]\n",
    "                cur += 1\n",
    "                i += 1\n",
    "            i0 = i\n",
    "            while i < n and pattern[i] == 'D':\n",
    "                i += 1\n",
    "            for j in range(i, i0 - 1, -1):\n",
    "                ans[j] = digits[cur]\n",
    "                cur += 1\n",
    "        return ''.join(ans)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
